package 学习;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * Keafmd
 *
 * @ClassName: BucketSort
 * @Description: 桶排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 13:32
 */
public class BucketSort {

    public static void bucketSort(int[] arr) {
        bucketSort(arr, true);
    }

    public static void bucketSort(int[] arr, boolean ascending) {
        if (arr == null || arr.length == 0) {
            return;
        }
        //计算最大值与最小值
//        int max = Integer.MIN_VALUE;
//        int min = Integer.MAX_VALUE;
//        for (int i = 0; i < arr.length; i++) {
//            max = Math.max(arr[i], max);
//            min = Math.min(arr[i], min);
//        }
        int min = Arrays.stream(arr).min().getAsInt();
        int max = Arrays.stream(arr).max().getAsInt();

        //计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArrs = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArrs.add(new ArrayList<>());
        }

        //将每个元素放入桶中
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - min) / (arr.length);
            bucketArrs.get(num).add(arr[i]);
        }

        //对每个桶进行排序
        for (int i = 0; i < bucketArrs.size(); i++) {
            //用系统的排序，速度肯定没话说
            Collections.sort(bucketArrs.get(i));
        }

        //将桶中元素赋值到原序列
        int index;
        if (ascending) {
            index = 0;
        } else {
            index = arr.length - 1;
        }

        for (int i = 0; i < bucketArrs.size(); i++) {
            ArrayList<Integer> bucketArr = bucketArrs.get(i);
            for (int j = 0; j < bucketArr.size(); j++) {
                arr[index] = bucketArr.get(j);
                if (ascending) {
                    index++;
                } else {
                    index--;
                }
            }

        }

    }

    public static void main(String[] args) {

        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
        int[] temparr;

        //测试桶排序
        System.out.println("测试桶排序:");
        temparr = nums.clone();
        BucketSort.bucketSort(temparr);
        //逆序排序
        //BucketSort.bucketSort(temparr,false);
        System.out.println(Arrays.toString(temparr));
    }
}